Random numbers are needed in a range of computing applications. One major example is the use of random numbers as keys in cryptography. Thus many cryptographic algorithms, such as the Data Encryption Standard (DES), utilise a key as part of the encryption process. In the case of DES, the key is 56 bits in length. DES is an example of a symmetric algorithm, in which the original (clear) data can only be retrieved from the encrypted data by inputting the same key into the decryption algorithm. Other known encryption algorithms are asymmetric, in that the encryption and decryption keys are distinct (although related by certain mathematical properties), but again such algorithms may use random numbers to initially generate key pairs.
It will be appreciated that the safety of encrypted data is only as good as the safety of the key; if the key is compromised, then the clear data is accessible. One way in which this can potentially happen is if the supposedly random numbers used for key generation turn out not to be properly random, since this can make the keys predictable, or at least more easily breakable. (Indeed, this is reported to have happened with one particular version of the Netscape Navigator system, see http://www.counterpane.com/yarrow.html; Netscape and Navigator are trademarks of Netscape Communications Corporation).
There are many other applications besides cryptography that also make use of random numbers. These include, or example, electronic and computer games, to provide variety and unpredictability in the game, simulators for system testing to generate random input data and then to assess the output, and so on. Accordingly, nearly all computer systems are equipped with some kind of facility to provide random numbers.
The random number generators (RNGs) used in such systems can be classified into two main types, namely pseudo-random and truly random. The former category is typically based on digital electronic devices, such as a linear feedback shift register (LFSR), as illustrated in FIG. 1. In an LFSR, a series of flip-flops (F4, F3, F2, and F1) are interconnected via two-input exclusive-or (XOR) gates. A first input to each XOR gate is the output of the preceding flop, while the second input to each XOR gate comes from a feedback loop (top rail in FIG. 1), back from the output of the shift register.
The links between the XOR gates and the feedback loop are via respective connectors, C3, C2, and C1 in FIG. 1. The behaviour of the shift register is altered according to whether these connectors are made open or shut. Although connectors C3, C2, and C1 could in principle be implemented as switches to provide a configurable system, in most implementations they are hard-wired as open or shut. An example is shown in FIG. 1A, where C3 and C1 from FIG. 1 are complete, while C2 is omitted. (For simplicity, FIG. 1A omits the XOR gate between flops F3 and F2, since this is redundant from a logic perspective, although in practice, for ease of construction, this XOR gate is likely to be present).
An LFSR can be represented by a polynomial, of order Xn, where n is the number of flops in the register. Thus the example of FIG. 1A can be denoted as: x4+x3+1. It will be appreciated that although the LFSRs in FIGS. 1 and 1A contain only 4 flops, most typical LFSRs will contains many more flops, for example 16, 32 or 64, and so will be represented by polynomials of appropriately higher order.
In use the LFSR is seeded with a certain pattern of values into the flops F4, F3, F2, and F1 (via a mechanism not shown in FIGS. 1 and 1A). Each clock input then causes these values to be shifted one flop along the register, in combination with the feedback signal (if connected for that flop), as well as producing an output from the final flop in the register, F1. It is known that for certain LFSR polynomials, the LFSR contents will cycle through all 2n−1 possible values, where n is the number of flops in the register, before repetition. LFSRs having this property are said to have maximal length. Note that the only value that does not occur in such a sequence is all zeroes. (This value also cannot be used for the initial seeding, since in this case the register contents and output will remain at all zeroes throughout).
LFSRs (especially those having maximal length) can be used as pseudo-random number generators. This is because the output sequence of such an LFSR fulfils many of the statistical tests for random numbers (e.g. approximately even numbers of zeroes and ones, and so on). Further details about LFSRs can be obtained for example in “The Art of Electronics” (see Sections 9.32–9.37) by Horowitz and Hill, Cambridge University Press, 1989, (ISBN 0-521-37095-7).
The output sequence of such an LFSR is only pseudo-random, in that if the structure polynomial) of the LFSR is known, then the future output can be determined absolutely, once the position within the maximal length sequence has been identified. This represents a potential exposure in a cryptographic system, in that once a hacker obtains knowledge of the LFSR polynomial and the identity of a single key provided by this system, then all future keys can be predicted. (Some limited trial and error may be required, if the known key does not allow sequence position to be uniquely determined, but the search space and hence available security is greatly compromised in comparison with the original situation, where all possible keys would have to be investigated).
It is clearly desirable therefore to provide a random number generator that outputs a truly (rather than pseudo-) random number sequence. Unfortunately, it is not possible to generate truly random numbers using the main digital components of a computer system, since these are specifically intended to be deterministic (there would be serious problems if the output from the computer were not reproducible).
Internet Request for Comments (rfc) 1750 discusses this issue. Various mechanisms for possibly generating truly random numbers based on external events (such as mouse inputs, or disk drive properties) are contemplated. However, these are generally unsatisfactory in that they may be difficult to generate in sufficient quantity and at the required speed for some applications, and they may also be susceptible to outside interception and/or manipulation. In addition, their randomness cannot be absolutely ensured.
It is therefore known to incorporate analog random number generators into semiconductor devices. The output of such devices depends on some underlying parameter (thermodynamic, quantum, etc.) that behaves in an inherently statistical manner. The most common approach is utilise a noise source as the origin of the randomness, and then sample this with an analog-to-digital converter (ADC). One example of a suitable noise source is a Zener diode (as described in “Analog Circuits Cookbook” by I Hickman, Newnes, 1995, ISBN 0 7506 2002 1), while the random number generator of U.S. Pat. No. 5,961,577 uses Johnson (thermal) noise for the underlying source of randomness. Thermal noise has also been adopted as the basis for a random number generator within the Intel Pentium III processor (Intel and Pentium are trademarks of Intel Corporation), as described in “The Intel Random Number Generator”, by B Jun and P Kocher, April 1999, available at http://www.cryptography.com/resources/whitepapers/IntelRNG.pdf.
Unfortunately, it is much more difficult to incorporate analog random number generators into processors and other digital devices (in comparison with LFSRs, for example). This is because LFSRs and other pseudo-random number generators can be fabricated from standard digital components, and so can be easily integrated into CMOS semiconductor devices (or any other similar technology). In contrast, an analog random number generator is normally far less compatible with the general structure and design of these (digital) semiconductor devices.
These compatibility and fabrication problems can potentially manifest themselves in terms of reduced reliability for analog random number generators relative to LFSRs and similar digital devices. Of particular concern is the situation where an analog random number generator fails in the field. Note that such a failure may be only partial (for example certain bits in an output word may become stuck at a particular value). Such a degree of failure may not be immediately apparent, and so a cryptographic system may continue to produce keys using these “random” numbers. However, it will be appreciated that in such circumstances the security of the system has been compromised, potentially severely. For example, if a hacker were to become aware of the deficiency mentioned above, then this would reduce the search space necessary to try to break a key in a brute force trial and error attack.